/**
 * 
 */
package linkedlist.passed2;

/**
 * @author xyyi
 *
 */
public class RotateList {

	/**
	 * Definition for singly-linked list.
	 */
	public class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}
	}

	/**
	Given a list, rotate the list to the right by k places, where k is non-negative.

	For example:
	Given 1->2->3->4->5->NULL and k = 2,
	return 4->5->1->2->3->NULL.
	 */
	public ListNode rotateRight(ListNode head, int n) {
		if (head == null || n == 0)
			return head;

		ListNode fast = head;
		ListNode slow = head;
		for (int i = 0; i < n; i++) {
			if (fast.next == null)
				return rotateRight(head, n % (i + 1));
			else
				fast = fast.next;
		}
		while (fast.next != null) {
			fast = fast.next;
			slow = slow.next;
		}

		fast.next = head;
		head = slow.next;
		slow.next = null;

		return head;
	}

	// Good for interview
    public ListNode rotateRight1(ListNode head, int k) {
        if (head == null || k == 0)
            return head;
        
        int size = 1; // pitfall, initial size should be 1, size only move size-1 steps
        ListNode tail = head;
        while (tail.next != null) {
            size++;
            tail = tail.next;
        }
        k = k % size;
        
        ListNode newHead = head;
        for (int i = 1, steps = size - k; i < steps; i++) {
            head = head.next;
        }
        
        tail.next = newHead;
        newHead = head.next;
        head.next = null;
        
        return newHead;
    }
	
	/**
	 * 
	 */
	public RotateList() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
